package algo.A05_其他排序算法;

import util.ArrayUtil;

/**
 * 开辟一个额外数组，扫描原数组，将数组中出现的数字的次数记录在额外数组对应的下标中，
 * 然后扫描额外数组，对原数组进行调回填，就排好序了
 * <p>
 * 当数据范围较小(小于1000)且已知最大值时，可以使用此方法，比快速排序还要快。
 * 不适用于数据范围很大且比较稀疏的数组，会特别浪费空间
 */
public class M04_计数排序 {
    public static void main(String[] args) {
        int max = 60;
        int[] arr = ArrayUtil.getRandomArr(20, 0, max);
        ArrayUtil.print(arr);
        countSort(arr,max);
        ArrayUtil.print(arr);
    }

    private static void countSort(int[] arr, int max) {
        int[] helper = new int[max + 1];
        for (int item : arr) {
            helper[item]++;
        }
        for (int i = 0, k = 0; i < helper.length; i++) {
            for (int j = 0; j < helper[i]; j++) {
                arr[k++] = i;
            }
        }
    }
}
